package com.example.androidtest1.proj.util;

import java.util.Arrays;
import java.util.HashSet;
import java.util.List;
import java.util.Set;
import java.util.Vector;

public class AISearcherImp implements Searcher {


    public static void main(String[] args) {
        System.out.println(new AISearcherImp().searchAll(new int[]{3, 2, 3, 6}));
        // System.out.println(search(new int[]{1, 4, 2, 3}));
        //  System.out.println(search(new int[]{1, 1, 1, 1}));
    }


    /**
     * 确定搜索器的实现v1.2
     * 枚举运算符的种类,构造出后缀表达式
     *
     * @param arr
     * @return
     */
    public List<String> search(int[] arr) {
        //4！*4^3*5=24*64*5=7680 <<7!*64=32w+
        for (int cc = 0; cc < FAC[4]; cc++) {
            int[] idx = codel(cc, 4);
            String a = String.valueOf(arr[idx[0]]);
            String b = String.valueOf(arr[idx[1]]);
            String c = String.valueOf(arr[idx[2]]);
            String d = String.valueOf(arr[idx[3]]);
            for (int i = 0; i < 4; i++)
                for (int j = 0; j < 4; j++)
                    for (int k = 0; k < 4; k++) {
                        String X = OPERATORS[i];
                        String Y = OPERATORS[j];
                        String Z = OPERATORS[k];
                        for (String[] ee : new String[][]{
                                {a, b, X, c, Y, d, Z},
                                {a, b, c, X, Y, d, Z},
                                {a, b, X, c, d, Y, Z},
                                {a, b, c, X, d, Y, Z},
                                {a, b, c, d, X, Y, Z},}) {
                            if (Math.abs(PostExpression.eval(ee) - TARGET) < EPS) {
                                return Arrays.asList(ee);
                            }
                        }
                    }
        }
        return null;
    }

    public Set<List<String>> searchAll(int[] arr) {
        Set<List<String>> lists = new HashSet<List<String>>();

        for (int cc = 0; cc < FAC[4]; cc++) {
            int[] idx = codel(cc, 4);
            String a = String.valueOf(arr[idx[0]]);
            String b = String.valueOf(arr[idx[1]]);
            String c = String.valueOf(arr[idx[2]]);
            String d = String.valueOf(arr[idx[3]]);
            for (int i = 0; i < 4; i++)
                for (int j = 0; j < 4; j++)
                    for (int k = 0; k < 4; k++) {
                        String X = OPERATORS[i];
                        String Y = OPERATORS[j];
                        String Z = OPERATORS[k];
                        for (String[] ee : new String[][]{
                                {a, b, X, c, Y, d, Z},
                                {a, b, c, X, Y, d, Z},
                                {a, b, X, c, d, Y, Z},
                                {a, b, c, X, d, Y, Z},
                                {a, b, c, d, X, Y, Z},}) {
                            if (Math.abs(PostExpression.eval(ee) - TARGET) < EPS) {
                                lists.add(new Vector(Arrays.asList(ee)));
                            }
                        }
                    }
        }
        return lists;
    }

    static final int FAC[] = {1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880};

    public static int[] codel(int x, int m) {
        int[] label = new int[m];
        int[] n = new int[m];
        int cnt;
        for (int i = 0; i < m; i++)
            label[i] = 1;
        for (int i = 0; i < m; i++) {
            cnt = x / FAC[m - 1 - i];
            x = x % FAC[m - 1 - i];
            for (int j = 0; j < m; j++) {
                if (label[j] == 0)
                    continue;
                if (cnt == 0) {
                    label[j] = 0;
                    n[i] = j;
                    break;
                }
                cnt--;
            }
        }
        return n;
    }

}
